package com.example.demo;

import org.junit.jupiter.api.Test;

public class NSort {

    private static  int[] arrs = {100,2 ,333333,1,4,3,6,5};
    @Test
    public void test(){


//        sort2(arrs);

        sort(arrs,0,arrs.length-1);
        sysOut(arrs);

    }

    //选出一个最小的 放到最前面,以此类推
    //选择排序
    private static void sort2(int[] arrs){
        //记录第几轮,第一轮对应0
       for(int i = 0;i<arrs.length;i++){
           //找出对应轮数最小的
           //最小的下表
           int min  = i;
           for(int j=i+1;j<arrs.length;j++){
               if(arrs[min]>arrs[j]){
                   min = j;
               }

           }

           swap(arrs,i,min);

       }
    }

    private static void sysOut(int []arrs){
        for(int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+"\t");
        }
    }
    //冒泡排序 length = 10 0-9

    private static void sort1(int[] arrs){
        for(int i = 0;i<=arrs.length-1;i++){
            boolean flag = true;
            for(int j = 0 ;j< arrs.length-1-i;j++){
                if(arrs[j]>arrs[j+1]){
                    swap(arrs,j+1,j);
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }

    }

    private static void swap(int arrs[] ,int j ,int k){
        int temp = arrs[j];
        arrs[j] = arrs[k];
        arrs[k] = temp;
    }


    public static void sort(int[] arr) {
        int[] tempArr = new int[arr.length];
        sort(arr, tempArr, 0, arr.length-1);
    }

    /**
     * 归并排序
     * @param arr 排序数组
     * @param tempArr 临时存储数组
     * @param startIndex 排序起始位置
     * @param endIndex 排序终止位置
     */
    private static void sort(int[] arr,int[] tempArr,int startIndex,int endIndex){
        if(endIndex <= startIndex){
            return;
        }
        //中部下标
        int middleIndex = startIndex + (endIndex - startIndex) / 2;

        //分解
        sort(arr,tempArr,startIndex,middleIndex);
        sort(arr,tempArr,middleIndex + 1,endIndex);

        //归并
        merge(arr,tempArr,startIndex,middleIndex,endIndex);
    }

    /**
     * 归并
     * @param arr 排序数组
     * @param tempArr 临时存储数组
     * @param startIndex 归并起始位置
     * @param middleIndex 归并中间位置
     * @param endIndex 归并终止位置
     */
    private static void merge(int[] arr, int[] tempArr, int startIndex, int middleIndex, int endIndex) {
        //复制要合并的数据
        for (int s = startIndex; s <= endIndex; s++) {
            tempArr[s] = arr[s];
        }

        int left = startIndex;//左边首位下标
        int right = middleIndex + 1;//右边首位下标
        for (int k = startIndex; k <= endIndex; k++) {
            if(left > middleIndex){
                //如果左边的首位下标大于中部下标,证明左边的数据已经排完了。
                arr[k] = tempArr[right++];
            } else if (right > endIndex){
                //如果右边的首位下标大于了数组长度,证明右边的数据已经排完了。
                arr[k] = tempArr[left++];
            } else if (tempArr[right] < tempArr[left]){
                arr[k] = tempArr[right++];//将右边的首位排入,然后右边的下标指针+1。
            } else {
                arr[k] = tempArr[left++];//将左边的首位排入,然后左边的下标指针+1。
            }
        }
    }

    //快速排序
    //选出一个基准值，比他小放左边 比他大的放右边 go on
    public static void sortQuick(int nums[]){
//        int biaozhun = nums[0];
//        int left  = 0 ;
//        int right = 0;
//        for (int i=1;i<nums.length;i++){
//            if(nums[i]>=biaozhun){
//                swap(nums,);
//            }
//        }

    }


    private static void sort(int[] arr,int startIndex,int endIndex) {
        if (endIndex <= startIndex) {
            return;
        }
        //切分
        int pivotIndex = partition(arr,startIndex,endIndex);
        sort(arr,startIndex,pivotIndex-1);
        sort(arr,pivotIndex+1,endIndex);
    }

    // 100 2 1 4 3 6 5
    private static int partition(int[] arr,int startIndex,int endIndex) {
        int pivot = arr[startIndex];//取基准值
        int mark = startIndex;//Mark初始化为起始下标

        for(int i=startIndex+1; i<=endIndex; i++){
            if(arr[i]<pivot){
                //小于基准值 则mark+1，并交换位置。
                mark ++;
//                swap(arr,mark,i);
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        //基准值与mark对应元素调换位置
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }



    private static int partition2(int[] arr,int startIndex,int endIndex) {
        int pivot = arr[startIndex];//取基准值
        int tmp = startIndex;
        for(int i =startIndex+1;i<=endIndex;i++){
            if(arr[i]<pivot){
                tmp++;
                swap(arr,i,tmp);
            }
        }
        return tmp;
    }



}
